- Introduction and Review
- Brief review of prerequisites
- Selected Topics in Convex Analysis and Optimization
- Introduction to convex sets and functions
- Convex set results: Separating hyperplane and Caratheodory's theorems
- Convex function results: Jensen's inequality and applications, Legendre-Fenchel transformation
- Lagrangian duality and Karush-Kuhn-Tucker (KKT) conditions
- Strong convexity and oracle complexity of gradient descent
- Gradient descent and its variants [optional]
- Foundations of Spectral Methods
- Positive semidefiniteness. Spectral and singular value decompositions
- Courant-Fischer-Weyl minimax theorems
- Perron-Frobenius theory [optional]
- Matrix norms and perturbation theory [optional]
- Concentration Inequalities and their Applications in CS
- Introduction to measure theory
- Markov, Chebyshev, and Chernoff Bounds
- Hoeffding and Bernstein inequalities
- Martingales, Azuma-Hoeffding bound, and McDiarmid's inequality
- Applications to learning theory (e.g., Glivenko-Cantelli)
- Talagrand's Inequality [optional]
- Discrete Fourier Analysis
- Introduction to discrete Fourier Analysis and Abelian groups
- Characters, bias, Fourier transform
- Parseval's and Plancherel's identities
- Blum-Luby-Rubinfeld (BLR) linearity testing
- Convolution and translation invariant systems
- Learning: The low-degree algorithms
- Selected Topics
- Applied analysis for Learning Theory
- Coding Theory
- Additional Randomized Techniques
- Additional Topics in Discrete Fourier Analysis
|